P2341 [HAOI2006]受欢迎的牛

这道题一看就是一道强连通分量的题，不会的可以参考我的博客。

当我们用$Tarjan$缩点之后，记新图点的个数为$cnt$。我们枚举原图的每一条边，计算新图中的点的出度。对于点$i$，我们把它的出度记为$Out[i]$。那么，会有以下几种情况：

1.没有一个$Out[i]$为0，说明每一个点至少有一条连向其他边的有向边，那么新图至少有$cnt$条边，一定会有一个环(因为$cnt-1$条边是一棵树，无论如何加边都会构成环)，但缩点后不可能有环，矛盾。

2.只有一个$Out[i]$为0，那么这个点一定受到所有奶牛的膜拜，（其他奶牛出度不为0，会膜拜其他奶牛，这样膜来膜去一定会汇集到出度为0的奶牛上，不理解的自行脑补一下）

3.有两个及以上的$Out[i]$为0，那么每个人至少得不到一群奶牛（已经缩点，可能不止一头）的支持。直接输出0。

综合以上三点，我们就可以写出正解了：

#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

const int MAXN = 10000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];
vector< int > lit_Graph[ MAXN + 5 ];
stack< int > s;

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth , cnt;
int belong[ MAXN + 5 ] , num[ MAXN + 5 ] , Out[ MAXN + 5 ];
bool is[ MAXN + 5 ];
void Tarjan( int u ) {
    dfn[ u ] = low[ u ] = ++ depth;
    is[ u ] = 1 , s.push( u );

    int v;
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        v = Graph[ u ][ i ];
        if( !dfn[ v ] ) {
            Tarjan( v );
            low[ u ] = min( low[ u ] , low[ v ] );
        }
        else if( is[ v ] )
            low[ u ] = min( low[ u ] , dfn[ v ] );
    }
    if( dfn[ u ] == low[ u ] ) {
        cnt ++;
        do{
            v = s.top( );
            is[ v ] = 0 , s.pop( );
            belong[ v ] = cnt;
            num[ cnt ] ++;
        }while( u != v );
    }
}

int main( ) {
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d",&x,&y);
        Graph[ x ].push_back( y );
    }
    for( int i = 1 ; i <= n ; i ++ )
        if( !dfn[ i ] ) Tarjan( i );
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
            int u = belong[ i ] , v = belong[ Graph[ i ][ j ] ];
            if( u != v ) {
                lit_Graph[ u ].push_back( v );
                Out[ u ] += num[ v ];
            }
        }
    int Ans = 0 , tot = 0;
    for( int i = 1 ; i <= cnt ; i ++ )
        if( Out[ i ] == 0 ) Ans += num[ i ] , tot ++;
    printf("%d",tot >= 2 ? 0 : Ans);
    return 0;
}